package com.example.usercenter.utils;

/**
 * 算法工具类
 * @author 米饭好好吃
 */
public class AlgorithmUtils {

    /**
     * 编辑距离算法
     * @param tagList1 标签列表1
     * @param tagList2 标签列表2
     * @return 最小编辑次数
     */
    public static int minDistance(String[] tagList1, String[] tagList2) {
        int len1 = tagList1.length;
        int len2 = tagList2.length;
        // 1. 状态表示：dp[i][j]表示tagList1的前i个字符串构成的数组变为tagList2的前j个字符串构成的数组的最少编辑次数
        int[][] dp = new int[len1 + 1][len2 + 1];
        // 2. 状态初始化
        for (int i = 0; i <= len2; i++) {
            dp[0][i] = i;
        }
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        // 3. 状态转移
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (tagList1[i - 1].equals(tagList2[j - 1])) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + dp[i][j - 1]; // 新增一个字符
                    dp[i][j] = Math.min(dp[i][j], 1 + dp[i - 1][j]); // 删除一个字符
                    dp[i][j] = Math.min(dp[i][j], 1 + dp[i - 1][j - 1]); // 修改一个字符
                }
            }
        }
        // 4. 返回值
        return dp[len1][len2];
    }

    public static void main(String[] args) {
        String[] matchTagList = { "Java", "大一", "篮球", "音乐" };
        String[] tagList1 = { "Java", "大一", "乒乓球", "跳舞" };
        String[] tagList2 = { "C++", "大二", "乒乓球" };
        System.out.println("1与2的编辑距离是：" + AlgorithmUtils.minDistance(tagList1, matchTagList));
        System.out.println("1与3的编辑距离是：" + AlgorithmUtils.minDistance(tagList2, matchTagList));
    }
}
